
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0839
 * @Author : WangRuoyu 
 * @Date : 2023/9/18 16:48
 */

#include "iostream"
#include "algorithm"

using namespace std;

const int N = 1e5 + 10;
int h[N], hp[N], ph[N];
int cnt = 0;
int num = 0;

void heap_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u) {
    int t = u;
    if (2 * u <= cnt && h[t] > h[2 * u]) t = 2 * u;
    if (2 * u + 1 <= cnt && h[t] > h[2 * u + 1]) t = 2 * u + 1;
    if (t != u) {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        heap_swap(u / 2, u);
        u /= 2;
    }
}

void insert(int x) {
    h[++cnt] = x;
    hp[cnt] = ++num;
    ph[num] = cnt;
    up(cnt);
}

void printMin() {
    printf("%d\n", h[1]);
}

void deleteMin() {
    heap_swap(1, cnt--);
    down(1);
}

void deleteK(int k) {
    int u = ph[k];
    heap_swap(u, cnt--);
    down(u);
    up(u);
}

void changeK(int k, int x) {
    int u = ph[k];
    h[u] = x;
    down(u);
    up(u);
}

int main() {
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        string op;
        int k, x;
        cin >> op;
        if (op == "I") {
            scanf("%d", &x);
            insert(x);
        } else if (op == "PM") {
            printMin();
        } else if (op == "DM") {
            deleteMin();
        } else if (op == "D") {
            scanf("%d", &k);
            deleteK(k);
        } else {
            scanf("%d %d", &k, &x);
            changeK(k, x);
        }
    }

    return 0;
}